#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef int Elemtype;
//定义树节点的基本结构
typedef struct BiTNode{
    Elemtype data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, *BiTree;

void visit(Elemtype data){
    printf(" %d ",data);
}

//三种遍历方式
//先序 根节点 - 左子树 - 右子树
void preOrder(BiTree T){
    if(T!=NULL){
        visit(T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

//中序  左子树 - 根节点 -右子树
void inOrder(BiTree T){
    if(T!=NULL){
        inOrder(T->lchild);
        visit(T->data);
        inOrder(T->rchild);
    }
}
//后序  左子树 - 右子树-根节点 
void postOrder(BiTree T){
    if(T!=NULL){
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T->data);
    }
}

//构建二叉树
BiTNode * createBiTree(Elemtype preOrderarr[],int preFirst,int preLast,Elemtype inOrderarr[],
int inFirst,int inLast){
    if(preFirst > preLast){
        return NULL;
    }
    BiTNode* root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = preOrderarr[preFirst];
    
    int rootIndex;
    for ( rootIndex = inFirst; rootIndex <= inLast; rootIndex++)
    {
        if(root->data == inOrderarr[rootIndex]){
            break;
        }
    }
    root->lchild = createBiTree(preOrderarr,preFirst+1,preFirst+rootIndex-inFirst,inOrderarr,inFirst,rootIndex-1);
    root->rchild = createBiTree(preOrderarr,preFirst+rootIndex-inFirst+1,preLast,inOrderarr,rootIndex+1,inLast);
    return root;
}

//链队列
typedef struct node
{
    BiTNode* data;
    struct node* next;
}node;

typedef struct Queue{
    node * front;
    node * rear;
}Queue;

//初始化node
node * initNode(){
    node * n= (node*)malloc(sizeof(node));
    return n;
}
//初始化队列
Queue * initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

//判断是否为空
int isQueueEmpty(Queue *q){
    if(q->front == NULL){
        return 1;
    }
    return 0;
}

//入队
void EnQueue(Queue *q,BiTNode * data){
    node * n = initNode();
    n->data = data;
    n->next = NULL;
    if(isQueueEmpty(q)){
        //入队后只有一个元素特殊处理
        q->front = n;
        q->rear = n;
    }else{
        q->rear->next = n;
        q->rear= n;
    }
}
//出队    
 BiTNode * DeQueue(Queue *q){
    node *n = q->front;
    if(isQueueEmpty(q)){
        return NULL;
    }
    //队列不为空
    if (q->front == q->rear)
    {//如果只有一个元素，front和rear都置为空
       q->front =NULL;
       q->rear = NULL;
    }else{
        q->front = q->front->next;
    }
    return n->data;
}

void levelTraverse(BiTree T){
    Queue *Q = initQueue();
    if(T !=NULL ){
        EnQueue(Q,T);
    }
    while (!isQueueEmpty(Q))
    {
      BiTNode *e = DeQueue(Q);
      visit(e->data);
      if(e->lchild!=NULL){
         EnQueue(Q,e->lchild);
      }
      if(e->rchild!=NULL){
         EnQueue(Q,e->rchild);
      }
    }
}

typedef struct SqStack
{
   BiTNode * data[MAXSIZE];
   int top;
}SqStack,*Stack;

//初始化栈
Stack initStack(){
    Stack s;
    s = (Stack)malloc(sizeof(SqStack));
    s->top = -1;
    return s;
}
//判断是否为空
int isStackEmpty(Stack s){
    if(s->top == -1){
        return 1;
    }
    return 0;
}
//出栈
void pop(Stack s,BiTNode **p){
    *p = s->data[s->top];
    s->top--;
}
//入栈
void push(Stack s,BiTNode *p){
    s->top++;
    s->data[s->top] = p;
}
/*
非递归遍历  使用栈进行遍历

*/
//非递归先序遍历 根 - 左子树 -右子树
void preOrder02(BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode != NULL||!isStackEmpty(stack))
    {
       if(pNode){
            //非空节点 一定是某个子树的根节点，第一次走到这里就是整个树的根节点
          
            //入栈
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
            //为空 左子树为空，那么就访问本树的右子树
            //出栈一个元素，一定是本树的根节点，通过它的rchild来访问右子树
            pop(stack,&pNode);      
            pNode = pNode->rchild;
       }
    }
}

//非递归中序遍历  左子树 -根 -右子树
void inOrder02(BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode != NULL||!isStackEmpty(stack))
    {
       if(pNode){
            //非空节点 一定是某个子树的根节点，第一次走到这里就是整个树的根节点
          
            //入栈
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
            //为空 左子树为空，那么就访问本树的右子树
            //出栈一个元素，一定是本树的根节点，通过它的rchild来访问右子树
            pop(stack,&pNode); 
            visit(pNode->data);     
            pNode = pNode->rchild;
       }
    }
}
//非递归后序遍历
//左子树 - 右子树 - 根
void postOrder02(BiTree T){
    BiTNode *pNode = T;
    BiTNode* r = NULL;//最后访问的节点，用来判断右子树是否被遍历过，如果右子树被访问，那么根节点一定是最后被访问的
    Stack stack = initStack();
    while (pNode!=NULL || !isStackEmpty(stack))
    {   //判断pNode是不是空
        if(pNode){
            //当前pnode为某个子树的根节点
            push(stack,pNode);
            pNode = pNode->lchild;//访问左子树
        }else{
            //当pnode为空，说明某个子树为空，需要根据原树根节点判断下一步去哪里
            pop(stack,&pNode);
            push(stack,pNode); // ;两步加起来可以仅获取但是不弹出栈顶元素
            //下一步就要判断右子树的状态：1.空/非空 2.遍历过/ 没有遍历过
            if(pNode->rchild && pNode->rchild != r){
                //当前树的右子树不为空，且没有被遍历过
                pNode = pNode->rchild;
                push(stack,pNode);
                pNode = pNode->lchild;
            }else{
                //当前树的右子树要么是空，要么被遍历过,所以可以遍历根节点
                pop(stack,&pNode);
                visit(pNode->data);
                r = pNode;
                pNode = NULL; // 跳到getTop那一步，以便观察下一步去做什么。 现在的状态是 左子树或者是右子树都已经访问了，下一步要访问的是右子树或者是上一层的根节点了。 
            }
        }
    }
    
}

/*
递归题目思路：
 1.原问题可以分解成子问题，子问题和原问题是一样处理逻辑
 2.分析边界条件 ：空树怎么处理
 3.假设 子树已经xxx，或者是子问题已经可以返回正确的结果。 一定要先假设这步可以返回正确的结果，脑海里不要去
 反复思考子问题的细节以及下一层的递归细节
 4.在假设上一步的基础上，需要利用得到的结果，保证这一层的结果是正确的
*/
//求二叉树的节点个数
int getTreeNodes(BiTree T){
    if(T == NULL){
        return 0;
    }
    return getTreeNodes(T->lchild) + getTreeNodes(T->rchild) +1;
}


int main(){
    int preArr[MAXSIZE] = {1,2,4,5,7,3,6};
    int inArr[MAXSIZE] = {4,2,7,5,1,3,6};
    BiTree T = createBiTree(preArr,0,6,inArr,0,6);
   int res =  getTreeNodes(T);
   printf("the res is %d\n",res);
}